package com.zrrd.zuo.kmp;

import java.lang.reflect.WildcardType;

/**
 * @author ywb
 * @Description:
 * @date 2023/5/1 21:37
 */
public class Class_KMP {
    //求str match str子串==match的初始值，存在则返回下标不存在返回-1
    public static int getIndexOf(String s1,String s2){
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] str = s1.toCharArray();
        char[] match = s2.toCharArray();
        int x = 0,y = 0;
        int[] next = getNextArray(match);
        while(x < str.length && y < match.length){
            if(str[x] == match[y]){
                x++;
                y++;
            }else if(next[y] == -1){//y == 0
                x++;
            }else {
                y = next[y];
            }
        }
        return y == match.length ? x - y : -1;
    }
    //构建前缀和后缀相等的最大个数 next数组
    public static int[] getNextArray(char[] match){
        if (match.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[match.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;//目前在哪个位置上求next数组的值
        int cn = 0;// 当前是哪个位置的值再和i-1位置的字符比较
        while(i < match.length){
            if(match[i - 1] == match[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
    }
    public static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (getIndexOf(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }

}

